The theory of constructive (recursive) models follows from works of Froehlich, Shepherdson, Mal'tsev, Kuznetsov, Rabin, and Vaught in the 50s. Within the framework of this theory, algorithmic properties of abstract models are investigated by constructing representations on the set of natural numbers and studying relations between algorithmic and structural properties of these models. This book is a very readable exposition of the modern theory of constructive models and describes methods and approaches developed by representatives of the Siberian school of algebra (...) and logic and some other researchers (in particular, Nerode and his colleagues). The main themes are the existence of recursive models and applications to fields, algebras, and ordered sets (Ershov), the existence of decidable prime models (Goncharov, Harrington), the existence of decidable saturated models (Morley), the existence of decidable homogeneous models (Goncharov and Peretyat'kin), properties of the Ehrenfeucht theories (Millar, Ash, and Reed), the theory of algorithmic dimension and conditions of autostability (Goncharov, Ash, Shore, Khusainov, Ventsov, and others), and the theory of computable classes of models with various properties. Future perspectives of the theory of constructive models are also discussed. Most of the results in the book are presented in monograph form for the first time. The theory of constructive models serves as a basis for recursive mathematics. It is also useful in computer science, in particular, in the study of programming languages, higher level languages of specification, abstract data types, and problems of synthesis and verification of programs. Therefore, the book will be useful for not only specialists in mathematical logic and the theory of algorithms but also for scientists interested in the mathematical fundamentals of computer science. The authors are eminent specialists in mathematical logic. They have established fundamental results on elementary theories, model theory, the theory of algorithms, field theory, group theory, applied logic, computable numberings, the theory of constructive models, and the theoretical computer science. (shrink)

The article is focused on studying the philosophical and legal nature of fundamental human rights and freedoms, which are interpreted as natural and inherent in a person from birth. It is shown that the “naturalness” of rights and freedoms is a legal fiction. In reality, natural rights and freedoms have a sociocultural, that is, “artificial” character. They strengthen the achieved level of guarantees of individual freedom and humanity in public relations.

The article is devoted to assessing the reasons and meaning of amendments to the Russian Federation Constitution made by the current political regime. The manner in which the amendments were adopted together with their content demonstrates inability of the state and the political system as a whole to govern and rule in accordance with the principles and norms of democracy and law. The concept of “unworthy governing” is used to characterize the existing mechanism of power and management of society in (...) Russia. (shrink)

The article deals with the problem of the cyclical nature of socio-historical development. Cyclicity is positioned as a universal feature of social development, making it possible to use the “lessons of history” in forecasting the future. Particular attention is paid to analyzing the causes of chronic disruptions in Russia’s modernization. The specificity of the Russian history cyclical nature is seen in the action of the institutional matrix, which unites authoritarianism and the suppression of private property into a monolithic whole.

In this article we study the problem of classifying φ-spaces with a fixed basis subspace. In the first part, this problem is treated in a more general topological context. The second part is devoted to effective φ-spaces.

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...) other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

We show that for every ordinal notation ξ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\xi}$$\end{document} of a nonzero computable ordinal, there exists a Σξ-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{-1}_\xi}$$\end{document}—computable family which up to equivalence has exactly one Friedberg numbering, which does not induce the least element in the corresponding Rogers semilattice.

In this paper, we prove several results about the Turing jumps of low c.e. sets. We show that only Δ‐levels of the Ershov Hierarchy can properly contain the Turing jumps of c.e. sets and that there exists an arbitrarily large computable ordinal with a normal notation such that the corresponding Δ‐level is proper for the Turing jump of some c.e. set. Next, we generalize the notion of jump traceability to the jump traceability with ‐ and ‐bound for every infinite (...) computable ordinal α. It is known that jump traceability and superlowness coincide on the c.e. sets and we show that for every infinite computable ordinal α, jump traceability with ‐ or ‐bound of a c.e. set A is equivalent to the fact that. Finally, we consider the generalized truth‐table reducibilities and prove that for every (not necessarily the Turing jump of a c.e. set) set A and every limit computable ordinal α, iff. (shrink)

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in (...) this context. (shrink)

We prove a number of elementary facts about computability in partial combinatory algebras. We disprove a suggestion made by Kreisel about using Friedberg numberings to construct extensional pca’s. We then discuss separability and elements without total extensions. We relate this to Ershov’s notion of precompleteness, and we show that precomplete numberings are not 1–1 in general.

Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the (...) Jump Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse. (shrink)

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δmath image sets, giving conditions under which a relation is intrinsically α-r. e.

We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.

The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δta 2 is just large enough to include several types of pointsets in Euclidean spaces ℝ k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class ΔB 2 and Ershov's hierarchy in the class Δ0 2 of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within Δta 2. This is based (...) on suitable characterizations of the sets from Δta 2 which are obtained in a close analogy to those of the ΔB 2 sets as well as those of the Δ0 2 sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω 2. Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented. (shrink)

It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ2 sets. Different equivalent characterisations of 1-genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1-genericity: in terms of sets of strings and in terms of density functions, as we (...) will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ02 sets are considered. While the string characterization of 1-genericity collapses at the second level of the difference hierarchy to 2-genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n-c.e. degrees for n ≥ 2. (shrink)

An Ax-Kochen-Ershov principle for intermediate structures between valued groups and valued fields. We will consider structures that we call valued B-groups and which are of the form $\langle G, B, *, v\rangle$ where - G is an abelian group, - B is an ordered group, - v is a valuation defined on G taking its values in B, - * is an action of B on G satisfying: ∀ x ∈ G ∀ b ∈ B v(x * b) = (...) v(x) · b. The analysis of Kaplanski for valued fields can be adapted to our context and allows us to formulate an Ax-Kochen-Ershov principle for valued B-groups: we axiomatise those which are in some sense existentially closed and also obtain many of their model-theoretical properties. Let us mention some applications: 1. Assume that v(x) = v(nx) for every integer n ≠ 0 and x ∈ G, B is solvable and acts on G in such a way that, for the induced action, $\mathbb{Z}[B] \setminus \{0\}$ embeds in the automorphism group of G. Then $\langle G, B, *, v\rangle$ is decidable if and only if B is decidable as an ordered group. 2. Given a field k and an ordered group B, we consider the generalised power series field k((B)) endowed with its canonical valuation. We consider also the following structure: $\mathbf{M} = \langle k((B))_+, S, v, \times \upharpoonright_{k((B))\times S}\rangle,$ where k((B)) + is the additive group of k((B)), S is a unary predicate interpreting ${T^b| b \in B}$ , and $\times \upharpoonright_{k((B))\times S}$ is the multiplication restricted to k((B))× S, structure which is a reduct of the valued field k((B)) with its canonical cross section. Then our result implies that if B is solvable and decidable as an ordered group, then M is decidable. 3. A valued B-group has a residual group and our Ax-Kochen-Ershov principle remains valid in the context of expansions of residual group and value group. In particular, by adding a residual order we obtain new examples of solvable ordered groups having a decidable theory. (shrink)

Computably enumerable equivalence relations received a lot of attention in the literature. The standard tool to classify ceers is provided by the computable reducibility \. This gives rise to a rich degree structure. In this paper, we lift the study of c-degrees to the \ case. In doing so, we rely on the Ershov hierarchy. For any notation a for a non-zero computable ordinal, we prove several algebraic properties of the degree structure induced by \ on the \ equivalence (...) relations. A special focus of our work is on the existence of infima and suprema of c-degrees. (shrink)

We show that the structure R of recursively enumerable degrees is not a Σ₁-elementary substructure of Dn, where Dn (n > 1) is the structure of n-r.e. degrees in the Ershov hierarchy.

In this thesis, we study Turing degrees in the context of classical recursion theory. What we are interested in is the partially ordered structures $\mathcal {D}_{\alpha }$ for ordinals $\alpha <\omega ^2$ and $\mathcal {D}_{a}$ for notations $a\in \mathcal {O}$ with $|a|_{o}\geq \omega ^2$.The dissertation is motivated by the $\Sigma _{1}$ -elementary substructure problem: Can one structure in the following structures $\mathcal {R}\subsetneqq \mathcal {D}_{2}\subsetneqq \dots \subsetneqq \mathcal {D}_{\omega }\subsetneqq \mathcal {D}_{\omega +1}\subsetneqq \dots \subsetneqq \mathcal {D}$ be a $\Sigma _{1}$ (...) -elementary substructure of another? For finite levels of the Ershov hierarchy, Cai, Shore, and Slaman [Journal of Mathematical Logic, vol. 12, p. 1250005] showed that $\mathcal {D}_{n}\npreceq _{1}\mathcal {D}_{m}$ for any $n < m$. We consider the problem for transfinite levels of the Ershov hierarchy and show that $\mathcal {D}_{\omega }\npreceq _{1}\mathcal {D}_{\omega +1}$. The techniques in Chapters 2 and 3 are motivated by two remarkable theorems, Sacks Density Theorem and the d.r.e. Nondensity Theorem.In Chapter 1, we first briefly review the background of the research areas involved in this thesis, and then review some basic definitions and classical theorems. We also summarize our results in Chapter 2 to Chapter 4. In Chapter 2, we show that for any $\omega $ -r.e. set D and r.e. set B with $D<_{T}B$, there is an $\omega +1$ -r.e. set A such that $D<_{T}A<_{T}B$. In Chapter 3, we show that for some notation a with $|a|_{o}=\omega ^{2}$, there is an incomplete $\omega +1$ -r.e. set A such that there are no a-r.e. sets U with $A<_{T}U<_{T}K$. In Chapter 4, we generalize above results to higher levels. We investigate Lachlan sets and minimal degrees on transfinite levels and show that for any notation a, there exists a $\Delta ^{0}_{2}$ -set A such that A is of minimal degree and $A\not \equiv _T U$ for all a-r.e. sets U.prepared by Cheng Peng.E-mail: [email protected]. (shrink)

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice L. (...) In this paper, we combine the Ershov Hierarchy and fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. In particular, we focus on the fuzzy n-c.e. sets which form the finite levels of this hierarchy. Intuitively, a fuzzy set is n-c.e. if its membership function can be approximated by changing monotonicity at most n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document} times. We prove that the Fuzzy Ershov Hierarchy does not collapse; that, in analogy with the classical case, each fuzzy n-c.e. set can be represented as a Boolean combination of fuzzy c.e. sets; but that, contrary to the classical case, the Fuzzy Ershov Hierarchy does not exhaust the class of all Δ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta ^0_2$$\end{document} fuzzy sets. (shrink)

Computability theorists have introduced multiple hierarchies to measure the complexity of sets of natural numbers. The Kleene Hierarchy classifies sets according to the first-order complexity of their defining formulas. The Ershov Hierarchy classifies limit computable sets with respect to the number of mistakes that are needed to approximate them. Biacino and Gerla extended the Kleene Hierarchy to the realm of fuzzy sets, whose membership functions range in a complete lattice. In this paper, we combine the Ershov Hierarchy and (...) fuzzy set theory, by introducing and investigating the Fuzzy Ershov Hierarchy. (shrink)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...) a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

In well-known papers ([A-K1], [A-K2], and [E]) J. Ax, S. Kochen, and J. Ershov prove a transfer theorem for henselian valued fields. Here we prove an analogue for henselian valued and ordered fields. The orders for which this result apply are the usual orders and also the higher level orders introduced by E. Becker in [B1] and [B2]. With certain restrictions, two henselian valued and ordered fields are elementarily equivalent if and only if their value groups (with a little (...) bit more structure) and their residually ordered residue fields (a henselian valued and ordered field induces in a natural way an order in its residue field) are elementarily equivalent. Similar results are proved for elementary embeddings and ∀-extensions (extensions where the structure is existentially closed). (shrink)

Of the various notions of reduction in the logical literature, relative interpretability in the sense of Tarskiet al. [6] appears to be the central one. In the present note, this syntactic notion is characterized semantically, through the existence of a suitable reduction functor on models. The latter mathematical condition itself suggests a natural generalization, whose syntactic equivalent turns out to be a notion of interpretability quite close to that of Ershov [1], Szczerba [5] and Gaifman [2].

We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset (...) '\iff X$ is $\omega$-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every $X$ such that $\emptyset ^{b}\leq_{bT}X\leq_{bT}\emptyset ^{2b}$, there is a $Y\leq_{bT}\emptyset ^{b}$ such that $Y^{b}\equiv_{bT}X$. (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite (but constructive) order types, consisting of complements of effectively exhaustible sets, as (...) well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Defining a class of sets to be uniform Δ02 if it is derived from a binary {0,1}{0,1}-valued function f≤TKf≤TK, we show that, for any C⊆DeC⊆De induced by such a class, there exists a high Δ02 degree c which is incomparable with every degree b ϵ Ce \ {0e, 0'e}. We show how this result can be applied to quite general subclasses of the Ershov Hierarchy and we also prove, as a direct corollary, that every nonzero low degree caps with (...) both a high and a nonzero low Δ02 degree. (shrink)

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how (...) the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (shrink)

The paper gives an overview of the main stages of the development of «The Siberian Journal of Philosophy». It is shown how the journal is permanently linked with the history of the Philosophy Faculty of Novosibirsk State University. The role of Academician Yu. L. Ershov in the development of professional philosophical education at NSU is revealed and explained. The Summer Philosophical Schools held by the Faculty and the Siberian Philosophical Seminar’s are noted as a main factors that formed the (...) philosophical community around the NSU. Today, the journal acts as an organizer of interaction within the professional community and represents the face of the university in the media space of Russian philosophy. The author believes that for twenty years the journal has earned authority and has become a notable phenomenon in the life of the philosophical community not only in Siberia, but throughout the country. (shrink)

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershov’s completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from (...) the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices. (shrink)

It is shown that the classes of discrete parts, A ∩ ℕk, of approximately resp. weakly decidable subsets of Euclidean spaces, A ⊆ ℝk, coincide and are equal to the class of ω-r. e. sets which is well-known as the first transfinite level in Ershov's hierarchy exhausting Δ02.

We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...) people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBe-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n ≥ 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system $(O,\, < _o )$ of ordinal notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that $u\, < _o \,v$ , then there are classes of c.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that— above "ω-many" corrections—it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of c.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBe-learning ω-correction grammars, where ω is any notation for the smallest infinite ordinal ω. (shrink)

We consider first-order theories of topological fields admitting a model-completion and their expansion to differential fields . We give a criterion under which the expansion still admits a model-completion which we axiomatize. It generalizes previous results due to M. Singer for ordered differential fields and of C. Michaux for valued differential fields. As a corollary, we show a transfer result for the NIP property. We also give a geometrical axiomatization of that model-completion. Then, for certain differential valued fields, we extend (...) the positive answer of Hilbert’s seventeenth problem and we prove an Ax–Kochen–Ershov theorem. Similarly, we consider first-order theories of topological fields admitting a model-companion and their expansion to differential fields, and under a similar criterion as before, we show that the expansion still admits a model-companion. This last result can be compared with those of M. Tressl: on one hand we are only dealing with a single derivation whereas he is dealing with several, on the other hand we are not restricting ourselves to definable expansions of the ring language, taking advantage of our topological context. We apply our results to fields endowed with several valuations. (shrink)

In [6] Messmer and Wood proved quantifier elimination for separably closed fields of finite Ershov invariant e equipped with a (certain) Hasse derivation. We propose a variant of their theory, using a sequence of e commuting Hasse derivations. In contrast to [6] our Hasse derivations are iterative.

An elementary theory T in a language L is (strongly) finitely inseparable if the set of logically valid sentences of L and the set of T-finitely refutable sentences are recursively inseparable. In §1 we establish a sufficient condition for the elementary theory of a class of BA's with operators to be finitely inseparable. This is done using the methods developed independently by M. Rabin and D. Scott (see [6]) on the one hand and by Ershov on the other (see (...) [2]). (shrink)

We prove various results connected together by the common thread of computability theory.First, we investigate a new notion of algorithmic dimension, the inescapable dimension, which lies between the effective Hausdorff and packing dimensions. We also study its generalizations, obtaining an embedding of the Turing degrees into notions of dimension.We then investigate a new notion of computability theoretic immunity that arose in the course of the previous study, that of a set of natural numbers with no co-enumerable subsets. We demonstrate how (...) this notion of $\Pi ^0_1$ -immunity is connected to other immunity notions, and construct $\Pi ^0_1$ -immune reals throughout the high/low and Ershov hierarchies. We also study those degrees that cannot compute or cannot co-enumerate a $\Pi ^0_1$ -immune set.Finally, we discuss a recently discovered truth-table reduction for transforming a Kolmogorov–Loveland random input into a Martin-Löf random output by exploiting the fact that at least one half of such a KL-random is itself ML-random. We show that there is no better algorithm relying on this fact, in the sense that there is no positive, linear, or bounded truth-table reduction which does this. We also generalize these results to the problem of outputting randomness from infinitely many inputs, only some of which are random.Abstract prepared by David J. Webb.E-mail: [email protected]: https://arxiv.org/pdf/2209.05659.pdf. (shrink)